#include <stdio.h>

#define N 10000
/**
 * Program 1.1 Quick-find solution to connectivity problem
 * -------------------------------------------------------
 * 算法框架：
 * - 初始化：为每个对象p构建一个以自己为元素的连通集set(p)；
 * - 循环输入整数对，对每个整数对`p-q`来说：
 *   - 查找p和q各自所属的连通集：set(p)=find(p)，set(q)=find(q)；
 *   - 如果set(p)==set(q)，则表示p和q已经连通；
 *   - 否则，合并set(p)和set(q)
 * 
 * -------------------------------------------------------
 * 问：如何表示和操作p所在的连通集set(p)?
 * 答：树。
 *    - 集合创建操作：初始，以每个对象为根节点构建树。
 *    - 集合合并操作：修改与p相连的所有对象(包括p)，让其指向q所在树的根节点。
 * 
 * 合并思路一：选择某个元素作为该连通集的代表，让所有其它属于这个集合的元素都指向它
 * 
 * 问：如何表示p和q连通？
 * 答：合并操作，即修改与p相连的所有对象(包括p)让其指向q所在树的根节点。
 * 
 * 问：如何检查p和q已经连通？
 * 答：p和q所在树的根节点是否相同。
 * 
 * 问：如何表示根节点？(很关键)
 * 答：链接指向自身的对象。
 * -------------------------------------------------------
 * 借助一个整数数组id，满足如下性质：
 * - p和q是连通的当且仅当p和q所在树的根节点相同
 * 
 * 答：如何表示和获取节点p所在树的根节点？
 * 答：id[p]
 * 
 * id[p]存储的是对象p所在树的根节点的索引
 * 
 * 实现思路：使用树来表示连通集，借助数组来实现。
 * - 初始化数组id的第i个元素值为i，即每个元素都指向自己。
 * - 循环读取输入，对每个输入整数对`p-q`对来说：
 *   - 如果id[p]==id[q](p和q所在树的根节点相同)，那么忽略该输入对，继续处理下一个输入对；
 *   - 否则，遍历整个id数组，将等于id[p]的所有数组元素值均修改为id[q]，即让p所在树里的所有元素指向q所在树的根节点；
 *   - 并输出该输入对；
 * -----------------------------------------------------
 * 编译
 * gcc -o QuickFind QuickFind.c
 * 
 * 运行
 * ./QuickFind
 * 3 4 4 9 8 0 2 3 5 6 2 9 5 9 7 3 4 8 5 6 0 2 6 1
 *
 */
int main(int argc, char **argv){
    int i, p, q, t;
    int id[N];

    //初始化id数组值为索引值
    for (i = 0; i < N; i++) {
        id[i] = i;
    }

    // 依次处理输入对：查找+合并
    while (scanf("%d %d\n", &p, &q) == 2) {
        //如果set(p)和set(q)相等，即id[p]==id[q]，则表示p和q相连
        if (id[p]==id[q]) {
            continue;
        }
        t = id[p];
        //否则，遍历整个id数组，将等于id[p]的元素值都修改为id[q]
        for (i = 0; i < N; i++) {
            if (id[i] == t) {
                id[i] = id[q];
            }
        }
        printf("%d %d\n", p, q);
    }
    return 0;
}